package A一周刷爆LeetCode.A基础班.I暴力递归;

/**
 * @author wei.zhao
 * @description: 能装下的最大价值
 * @date 2022年04月19日 11:17
 */
public class Code06_Knapsack {

    public static void main(String[] args) {
        int[] weights = { 3, 2, 4, 7 };
        int[] values = { 5, 6, 3, 19 };
        int bag = 11;
        System.out.println(maxValue(weights, values, bag));
        System.out.println(maxValue(weights, values, bag));
    }

    public static int maxValue(int[] weights, int[] values, int bag) {
        return process(weights, values, bag, 0, 0, 0);
    }

    /**
     * weight：当前选择的所有物品的重量。
     * value：当前选择的所有物品的价值
     * i：当前选择到的物品索引位
     */
    private static int process(int[] weights, int[] values, int bag, int weight, int value, int i) {
        if (weight > bag) {
            return 0;
        }
        if (i > weights.length - 1) {
            return value;
        }
        int process01 = process(weights, values, bag, weight, value, i + 1);
        int process02 = process(weights, values, bag, weight + weights[i], value + values[i], i + 1);
        return Math.max(process01, process02);
    }

}
